package org.bear.linkList;

import java.util.ArrayList;
import java.util.HashMap;

/*
    138.随机链表的复制
 */
public class CopyRandomList {

    public Node copyRandomList(Node head) {
        Node newHead = new Node(-1);
        Node np = newHead;
        Node p = head;
        HashMap<Node, Node> map = new HashMap<Node, Node>();
        while (p != null) {
            Node node = new Node(p.val);
            np.next = node;
            np = np.next;
            map.put(p, node);
            p = p.next;
        }
        p = head;
        np = newHead.next;
        while (p != null) {
            np.random = map.get(p.random);
            p = p.next;
            np = np.next;
        }
        return newHead.next;
    }
}
